package tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;


/**使用孩子-兄弟表示法作为存储结构，实现树的先根、后根遍历和层次遍历
 * */
public class TraverseCBTree<AnyType> {
	
	public List<AnyType> preOrderList = new ArrayList<AnyType>();
	public List<AnyType> postOrderList = new ArrayList<AnyType>();
	public List<AnyType> levelOrderList = new ArrayList<AnyType>();
	
	/**先根遍历
	 * */
	public List<AnyType> preOrder(CBNode<AnyType> t){
		if(t!=null){
			/**访问根节点*/
			preOrderList.add((AnyType)t.getData());
			/**遍历左子树*/
			preOrder(t.getChildren());
			/**遍历右子树*/
			preOrder(t.getBrother());
		}
		return preOrderList;
	}
	
	
	/**后根遍历
	 * */
	public List<AnyType> postOrder(CBNode<AnyType> t){
		if(t!=null){
			/**遍历左子树*/
			postOrder(t.getChildren());
			/**访问根节点*/
			postOrderList.add((AnyType)t.getData());
			/**遍历右子树*/
			postOrder(t.getBrother());
		}
		return postOrderList;
	}
	
	
	/**层次遍历
	 * */
	public List<AnyType> levelOrder(CBNode<AnyType> root) {
		if (root == null)
			return null;
		//初始化一个队列
		Queue queue = new ArrayDeque<CBNode>();
		//把根节点加入到队列中,因为Queue继承了Collection方法
		queue.add(root);
		//当该队列不为空时
		while (!queue.isEmpty()) {
			
			CBNode<AnyType> temp = (CBNode) queue.poll();
			
			levelOrderList.add((AnyType)temp.getData());
			
			//按照层次加入到队列中
			
			if (temp.getChildren() != null) {
				
				queue.add(temp.getChildren());
				
			}
			if (temp.getBrother()!= null){
				queue.add(temp.getBrother());
				
			}
			
		}
		return levelOrderList;
	}
	
	//测试函数
	public static void main(String[] args) {
		
		ChildrenBrother<Character> cb=new ChildrenBrother<Character>();
		Scanner in=new Scanner(System.in);
		System.out.println("请输入字符串，以先序的顺序创建创建二叉树：");
		//供测试数字串 :ABDH I  EJ K   CFL MP Q R    GN    
		String str=in.nextLine();
		/**将字符串转换成字符数组*/
		char[] tree=str.toCharArray();
		/**创建包装类的数组*/
		Character[] preOrder = new Character[tree.length];
		/**遍历数组，景数组中非空格的字符包装后，存入包装类数组，对空格字符赋值为null*/
		for(int i=0;i<tree.length;i++){
			if(tree[i]==' '){
				preOrder[i]=null;
			}else{
//				preOrder[i]=new Character(tree[i]);
				preOrder[i]=tree[i];
			}
		}
		cb.rootNode=cb.createTreeByChildAndBrother(preOrder);
		
		//测试各种方法
		TraverseCBTree t=new TraverseCBTree();
		List<Character> list = new ArrayList<Character>();
		Iterator itr= null;
		//得到先跟遍历结果
		list=t.preOrder(cb.rootNode);
		itr = list.iterator();
		System.out.println("先跟遍历结果的结果为：");
		while(itr.hasNext()){
			System.out.print(itr.next()+"  ");
		}
		System.out.println("");
		
		//得到后跟遍历结果
		list=t.postOrder(cb.rootNode);
		itr = list.iterator();
		System.out.println("后跟遍历结果的结果为：");
		while(itr.hasNext()){
			System.out.print(itr.next()+"  ");
		}
		System.out.println("");
		
		//得到层次遍历结果
		list=t.levelOrder(cb.rootNode);
		itr = list.iterator();
		System.out.println("层次遍历结果的结果为：");
		while(itr.hasNext()){
			System.out.print(itr.next()+"  ");
		}
		System.out.println("");
		
	}

}
